package com.lmz.project.redis.arithmetic.sort;

/**
 * 快速排序
 */
public class QuickSort {
    static int[] arr = {1, 5, 2, 4, 3};
    public static int left;
    public static int right;

    public static int first;
    public static int end;

    public static void main(String[] args) {
//        quickSort1(0, arr.length - 1);
//        quickSort2(0,arr.length -1);
        quickSort3(0,arr.length -1);
        //遍历arr
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
    }


    public static void quickSort1(int l, int r) {
        if (l >= r) {
            return;
        }
        int x = arr[l + (int) (Math.random() * (r - l) + 1)];
        int mid = partition1(l, r, x);
        quickSort1(l, mid - 1);
        quickSort1(mid + 1, r);
    }

    public static void quickSort2(int l, int r) {
        if (l >= r) {
            return;
        }
        int x = arr[l + (int) (Math.random() * (r - l) + 1)];
        partition2(l, r, x);
        int ll = left;
        int rr = right;
        quickSort2(l, ll -1);
        quickSort2(rr + 1, r);
    }


    public static int partition1(int l, int r, int x) {
        //如果<=x
        int a = l, xi = 0;
        for (int i = l; i <= r; i++) {
            if (arr[i] <= x) {
                swap(i, a);
                if (x == arr[a]) {
                    xi = a;
                }
                a++;
            }
        }
        swap(a - 1, xi);
        return a - 1;
    }

    public static void partition2(int l, int r, int x) {
        left = l;
        right = r;
        //三条分支
        //1.如果 < x a和i 交换 a++.i++
        //2.如果 == x i++,a不变
        //3.如果 >x i和b交换，b--,i不变
        for (int i = l; i <= right; ) {
            if (arr[i] < x) {
                swap(left, i);
                left++;
                i++;
            } else if (arr[i] == x) {
                i++;
            } else {
                swap(right, i);
                right--;
            }
        }
    }


    public static void quickSort3(int l,int r){
        if (l>=r){
            return;
        }
        //随机获取一个数
        int x = arr[l + (int) (Math.random() * (r-l) + 1)];
        partition3(l,r,x);
        int l3 = first;
        int r3 = end;
        quickSort3(l,l3-1);
        quickSort3(r3+1,r);

    }

    private static void partition3(int l, int r, int x) {
        first = l;
        end = r;
        int i = l;
        while (i <= end){
            //三条分支
            //1.如果 < x a和i 交换 a++.i++
            //2.如果 == x i++,a不变
            //3.如果 >x i和b交换，b--,i不变
            if (arr[i] == x){
                i++;
            }else if (arr[i] < x){
                swap(first++,i++);
            }else {
                swap(i,end--);
            }
        }
    }


    public static void swap(int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
}
